package dp;

import org.junit.Test;

/**
 * @Description 剑指 Offer 63. 股票的最大利润
 * @Author Firenut
 * @Date 2023-03-24 23:32
 */
public class T63_maxProfit {
    @Test
    public void test() {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
//        [2,4,1]
    }

    // dp简化: 因为dp[i]只与dp[i-1]有关，可以不用定义dp数组
    public int maxProfit(int[] prices) {
//        if (prices.length == 0) {
//            return 0;
//        }
        int min = Integer.MAX_VALUE, max = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            } else if (prices[i] - min > max){
                max = prices[i] - min;
            }
        }
        return max;
    }

    // 法2: dp
    // 状态定义: dp[i]表示前i天可获得的最大利润
    // 初始值: dp[0]=0,第一天的利润是0
    // 转移方程: dp[i] = max(dp[i-1],prices[i]-min)
    // 返回值: dp[prices.length-1]
    // 时间复杂度: O(n)
    public int maxProfit3(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int dp[] = new int[prices.length]; // dp[i]表示前i天最大的利润
        dp[0] = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
                dp[i] = i > 0 ? dp[i - 1] : 0;
            } else {
                if (prices[i] - min > dp[i - 1]) {
                    dp[i] = prices[i] - min;
                } else {
                    dp[i] = dp[i - 1];
                }
            }
        }
        return dp[dp.length - 1];
    }

    // 法1:暴力解法
    public int maxProfit1(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[j] - prices[i] > max) {
                    max = prices[j] - prices[i];
                }
            }
        }
        return max;
    }
}

//    error:
//    public int maxProfit(int[] prices) {
//        int p = 0, q = 0;
//        int min = Integer.MAX_VALUE, max = 0;
//        for (int i = 0; i < prices.length; i++) {
//            if (prices[i] < min) {
//                min = prices[i];
//                p = i;
//            }
//            if (prices[i] > max && i > p) {
//                max = prices[i];
//                q = i;
//            }
//        }
//        if (p > q) {
//            return 0;
//        } else {
//            return prices[q] - prices[p];
//        }
//    }